package com.itzmn.newcode.offer;


import javax.swing.tree.TreeNode;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/13 15:12
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 判断一棵树是否是另一颗树的子树
 *
 *   构建二叉搜索树：
 *    如果根节点为空，创建根节点
 *    判断值与根节点哪个大，如果大于，放入右边，如果小于，放入左边
 *
 *   如何判断一个数是另一颗树的子树：
 *
 *    查到相同的根节点，然后去判断左右子树是否一样
 */
public class HasSubTree {

    public static void main(String[] args) {

        new HasSubTree().init();
    }
    public void init(){

        int[] ints = {7,5,8,3,6,9,2};
        int[] ints2 = {5,3,6,1};
        TreeNode binSearchTree = createBinSearchTree(ints);
        TreeNode binSearchTree2 = createBinSearchTree(ints2);
        xianxu(binSearchTree);
        boolean b = hasSubtree(binSearchTree, binSearchTree2);
        System.out.println(b);

    }

    /**
     * 判断2是否是1的子树
     * @param root1
     * @param root2
     * @return
     */
    public boolean hasSubtree(TreeNode root1, TreeNode root2) {

        boolean result = false;

        if (root1 != null && root2 != null){


            //根节点值一样
            if (root1.val == root2.val){

                //比较左右子树是否一样
                result = doHasTree(root1, root2);

            }
            if (!result){
                result = hasSubtree(root1.left,root2);
            }
            if (!result){
                result = hasSubtree(root1.right,root2);
            }


        }

        return result;
    }

    /**
     * 判断左右子树是否相同
     * @param node1
     * @param node2
     * @return
     */
    public boolean doHasTree(TreeNode node1,TreeNode node2){


        //如果Tree2已经遍历完了都能对应的上，返回true
        if (node2 == null) {
            return true;
        }
        //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
        if (node1 == null) {
            return false;
        }
        //如果其中有一个点没有对应上，返回false
        if (node1.val != node2.val) {
            return false;
        }

        //如果根节点对应的上，那么就分别去子节点里面匹配
        return doHasTree(node1.left,node2.left) && doHasTree(node1.right,node2.right);
    }


    /**
     *  先序遍历
     * @param RoottreeNode
     */
    private  void xianxu(TreeNode RoottreeNode) {

        if (RoottreeNode!=null){
            System.out.print(RoottreeNode.val+" ");
            //查找左节点
            xianxu(RoottreeNode.left);
            //查找右节点
            xianxu(RoottreeNode.right);
        }
    }


    /**
     *  根据数组创建二叉搜索树
     * @param arrs
     * @return
     */
    public TreeNode createBinSearchTree(int[] arrs){

        if (arrs.length==0){
            return null;
        }
        TreeNode root = new TreeNode(arrs[0]);

        TreeNode temproot = root;

        for (int i=1;i<arrs.length;i++){

            while (temproot != null){
                //如果传入的值比根节点大
                if (arrs[i]>=temproot.val){

                    //如果该节点存在右子节点，转换根节点
                    if (temproot.right!=null){
                        temproot = temproot.right;
                    }
                    //如果不存在右子节点，直接将数据插入右子节点
                    else {
                        TreeNode treeNode = new TreeNode(arrs[i]);
                        temproot.right =treeNode;
                        temproot = root;
                        break;
                    }
                }
                //如果传入的值比根节点小
                else {

                    if (temproot.left!=null){
                        temproot = temproot.left;
                    }else {
                        TreeNode treeNode = new TreeNode(arrs[i]);
                        temproot.left=treeNode;
                        temproot = root;
                        break;
                    }

                }
            }

        }
        return root;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}
